Practice | GeeksforGeeks | A computer science portal for geeks
LIVE   BATCHES

This track of the course covers the topic "Trees".

In details, this track will cover:

  • Basics: Introduction to the tree data structure. How exactly is it represented?
  • Operations: Creation, Insertion, Deletion and other operations like LCA.
  • Implementation: How to implement Trees.
  • Traversals: We'll look at inorder, preorder, postorder, level order and various other traversals.

Objective: The objective of this track is to familiarize the learners with Trees.

Track Content:

  • 4 Video Lecture on Trees.
  • Theoretical Articles.
  • Programming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.

Tree Data Structure is used to organise data in hierarchical manner.
In this video we discuss about:
node,root,leaf,child,parent,subtree,descendants,ancestors,degree and internal nodes.


In this video, we discuss applications of Trees:

  • To represent hierarchical data.
  • Binary Search Trees.
  • Binary heap
  • B and B+ Trees in DBMS
  • Spanning and Shortest path in computer networks
  • Parse Tree and Expression Tree in Compilers.

In Binary Tree every node has at most two children.
In this video, we further discuss the implementation to represent a Binary Tree.
Codes:


Tree Traversal is basically going through every node(key) exactly once.
In this video we briefly discuss:
Types of Tree Traversal i.e. Breadth-First Search(BFS) and Depth First Search(DFS).
Inorder, preorder and postorder traversals.


Implementation of Inorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print inorder traversal of the Tree whose nodes are given.
Codes:


Implementation of Preorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Preorder traversal of the Tree whose nodes are given.
Codes:


Implementation of Postorder Traversal
In this video, we discuss a function that takes root as a parameter, whose return type is void and is supposed to print Postorder traversal of the Tree whose nodes are given.
Codes:


Height of Binary Tree is the number of nodes between the longest path from root to leaf node(including the root and leaf node).
In this video we discuss about a recursive function that takes root of the tree and returns the height of the Binary Tree.
Codes:


Nodes at distance k from the root are basically the nodes at (k+1)th level of the Binary Tree.
In this video, we discuss a function that takes root and k as a parameter, whose return type is void and is supposed to print the nodes at distance k from the root.
Codes:


Level order traversal of a tree is breadth first traversal of binary tree.
In this video we will discuss about a function that takes root as a parameter, doesn’t returns anything and prints the level order traversal in a single line.we implement this function using queue datastructure.
Codes:


In Level Order Traversal Line by Line, we print the nodes at each level separately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-1.
In method-1, we implement this function using a single loop.
Codes:


In Level Order Traversal Line by Line, we print the nodes at each level seperately in a new line.
In this video we discuss:
A function that takes root as a parameter, doesn’t return anything and prints the level order traversal line by line by using method-2.
In method-2, we implement this function using nested loops.
Codes:


Size of Binary Tree is the total numbers of nodes present in that Tree.
In this video, we discuss a recursive function that takes root as a parameter and is supposed to return the size of the Tree whose nodes are given.
Codes:


Largest node(key) in a Tree is the maximum of the Tree.
In this video, we discuss a recursive function that takes the root of a binary Tree and returns the maximum of the Tree.
Codes:


To Print Left View of Binary Tree we need to print the leftmost node at every level of the Binary Tree.
In this video we discuss two methods to print left view of a given Binary Tree.In Method-1 we use Recursive method whereas in Method-2 we use the Iterative method approach by using queue datastructure.
Codes:


Children Sum Property is a property in which the sum of values of the left child and right child should be equal to the value of their node if both children are present. Else if only one child is present then the value of the child should be equal to its node value.
In this video, we discuss a recursive function that takes the root node as a parameter and returns TRUE if the Tree follows C.S.P. and FALSE if the Tree does not follow C.S.P.
Code:


In a Balanced Binary Tree for every node, the difference between heights of left subtree and right subtree should not be more than one.
In this video we discuss two solutions (one with time complexity of O(n^2) and another with time complexity of O(n) ) to check whether a Tree is Balanced or not.
Codes:


Maximum Width of Binary tree is the maximum number of nodes present in a level of the Tree.
In this video, we discuss a function that takes the root of a Binary Tree and returns the maximum width of the Binary Tree.
Hint:- we use level order traversal line by line logic to find maximum width of the Binary Tree.
Codes:


In this video we discuss:
Inorder conversion of Binary Tree to Doubly Linked List.
A function that takes root of a Binary Tree and converts it into a Doubly linked list.
Hint:- we need to do the inorder traversal of the Tree and while doing inorder traversal we can simply maintain a previous pointer or reference of the previously traversed node. And change right child of the previous node to current node and left child of current node as previous.
Codes:


This video discusses the Construction of a Binary Tree from Inorder and Preorder traversal.
Codes:


Introduction to LCA (Lowest Common Ancestor) problem and a O(n) solution to the problem.
Codes:


An efficient solution is discussed in this video. The solution does only one traversal of binary tree, but assumes that both keys exist in the binary tree.
Codes:


We are given a binary tree and a leaf node, we need to find time to burn the Binary Tree if we burn the given leaf at 0-th second. 
Codes:


Given a binary tree, our task is to count toal nodes.  Two methods are discussed here, naive method which is O(n).  And an efficient method which is O(Log n * Log n)
Codes:


This video talks about serialize and deserialize a binary tree. It discusses preorder traversal based approach.
Codes:


The video discisses stack based inorder traversal.


A O(n) extra space and O(n) time solution is discussed.


A O(h) extra space and O(n) time solution is discussed.

A Tree is a non-linear data structure where each node is connected to a number of nodes with the help of pointers or references.

A Sample tree is as shown below:


Basic Tree Terminologies:
  • Root: The root of a tree is the first node of the tree. In the above image, the root node is the node 30.
  • Edge: An edge is a link connecting any two nodes in the tree. For example, in the above image there is an edge between node 11 and 6.
  • Siblings: The children nodes of same parent are called siblings. That is, the nodes with same parent are called siblings. In the above tree, nodes 5, 11, and 63 are siblings.
  • Leaf Node: A node is said to be the leaf node if it has no children. In the above tree, node 15 is one of the leaf nodes.
  • Height of a Tree: Height of a tree is defined as the total number of levels in the tree or the length of the path from the root node to the node present at the last level. The above tree is of height 2.

Binary Tree

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child, or 2 child nodes.

Below is a sample Binary Tree:


Properties of a Binary Tree:
  1. The maximum number of nodes at level 'l' of a binary tree is (2l - 1). Level of root is 1.

    This can be proved by induction.
    For root, l = 1, number of nodes = 21-1 = 1
    Assume that the maximum number of nodes on level l is 2l-1.
    Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2l-1.
  2. Maximum number of nodes in a binary tree of height 'h' is (2h – 1).
    Here height of a tree is the maximum number of nodes on the root to leaf path. The height of a tree with a single node is considered as 1.
    This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2h-1. This is a simple geometric series with h terms and sum of this series is 2h – 1.
    In some books, the height of the root is considered as 0. In that convention, the above formula becomes 2h+1 – 1.
  3. In a Binary Tree with N nodes, the minimum possible height or the minimum number of levels is Log2(N+1). This can be directly derived from point 2 above. If we consider the convention where the height of a leaf node is considered 0, then above formula for minimum possible height becomes Log2(N+1) – 1.
  4. A Binary Tree with L leaves has at least (Log2L + 1) levels. A Binary tree has maximum number of leaves (and minimum number of levels) when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.
       L   <=  2l-1  [From Point 1]
    l = Log2L + 1
    where l is the minimum number of levels.
  5. In a Binary tree in which every node has 0 or 2 children, the number of leaf nodes is always one more than the nodes with two children.
       L = T + 1
    Where L = Number of leaf nodes
    T = Number of internal nodes with two children

Types of Binary Trees: Based on the structure and number of parents and children nodes, a Binary Tree is classified into the following common types:
  • Full Binary Tree: A Binary Tree is full if every node has either 0 or 2 children. The following are examples of a full binary tree. We can also say that a full binary tree is a binary tree in which all nodes except leave nodes have two children.






    In a Full Binary, the number of leaf nodes is number of internal nodes plus 1.
  • Complete Binary Tree: A Binary Tree is a complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

    Following are the examples of Complete Binary Trees:



  • Perfect Binary Tree: A Binary tree is a Perfect Binary Tree when all internal nodes have two children and all the leave nodes are at the same level.

    Following are the examples of Perfect Binary Trees:



    A Perfect Binary Tree of height h (where height is the number of nodes on the path from the root to leaf) has 2h – 1 node.
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc.), which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees:

Example Tree

  • Inorder (Left, Root, Right) : 4 2 5 1 3
  • Preorder (Root, Left, Right) : 1 2 4 5 3.
  • Postorder (Left, Right, Root) : 4 5 2 3 1

Let's look at each of these tree traversal algorithms in details:
  • Inorder Traversal: In Inorder traversal, a node is processed after processing all the nodes in its left subtree. The right subtree of the node is processed after processing the node itself.
    Algorithm Inorder(tree)
    1. Traverse the left subtree, i.e.,
    call Inorder(left->subtree)
    2. Visit the root.
    3. Traverse the right subtree, i.e.,
    call Inorder(right->subtree)
    Example: Inorder traversal for the above-given tree is 4 2 5 1 3.
  • Preorder Traversal: In preorder traversal, a node is processed before processing any of the nodes in its subtree.

    Algorithm Preorder(tree)
    1. Visit the root.
    2. Traverse the left subtree, i.e.,
    call Preorder(left-subtree)
    3. Traverse the right subtree, i.e.,
    call Preorder(right-subtree)
    Example: Preorder traversal for the above-given tree is 1 2 4 5 3.
  • Postorder Traversal: In post order traversal, a node is processed after processing all the nodes in its subtrees.
    Algorithm Postorder(tree)
    1. Traverse the left subtree, i.e.,
    call Postorder(left-subtree)
    2. Traverse the right subtree, i.e.,
    call Postorder(right-subtree)
    3. Visit the root.
    Example: Postorder traversal for the above-given Tree is 4 5 2 3 1.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1

One more example:

We have seen the three basic traversals(Preorder, postorder, and Inorder) of a Binary Tree. We can also traverse a Binary Tree using the Level Order Traversal.

In the Level Order Traversal, the binary tree is traversed level-wise starting from the first to last level sequentially.

Consider the below binary tree:


The Level Order Traversal of the above Binary Tree will be: 10 20 30 40 50 60 70 80.

Algorithm: The Level Order Traversal can be implemented efficiently using a Queue.
  1. Create an empty queue q.
  2. Push the root node of tree to q. That is, q.push(root).
  3. Loop while the queue is not empty:
    • Pop the top node from queue and print the node.
    • Enqueue node's children (first left then right children) to q
    • Repeat the process until queue is not empty.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
1 2 3 4 5

Time Complexity: O(N), where N is the number of nodes in the Tree.
Auxiliary Space: O(N)
Problem: Given a Binary Tree and a Key. The task is to insert the key into the binary tree at first position available in level order.



The idea is to do iterative level order traversal of the given tree using a queue. If we find a node whose left child is empty, we make new key as the left child of the node. Else if we find a node whose right child is empty, we make new key as the right child of that node. We keep traversing the tree until we find a node whose either left or right child is empty.

Below is the implementation of this approach:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Inorder traversal before insertion: 7 11 10 15 9 8 
Inorder traversal after insertion: 7 11 12 10 15 9 8
Problem: Given a Binary Tree and a node to be deleted from this tree. The task is to delete the given node from it.

Examples:
Delete 10 in below tree

Output :



Delete 20 in below tree

Output :


While performing the delete operation on binary trees, there arise a few cases:
  1. The node to be deleted is a leaf node. That is it does not have any children.
  2. The node to be deleted is a internal node. That is it have left or right child.
  3. The node to be deleted is the root node.

In the first case 1, since the node to be deleted is a leaf node, we can simply delete the node without any overheads. But in the next 2 cases, we will have to take care of the children of the node to be deleted.

In order to handle all of the cases, one way to delete a node is to:
  1. Starting at the root, find the deepest and rightmost node in binary tree and node which we want to delete.
  2. Replace the deepest rightmost node’s data with the node to be deleted.
  3. Then delete the deepest rightmost node.


Below is the implementation of the above approach:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Inorder traversal before Deletion: 7 11 12 10 15 9 8 
Inorder traversal after Deletion: 7 8 12 10 15 9
Given a Binary Tree and the value of two nodes n1 and n2. The task is to find the lowest common ancestor of the nodes n1 and n2 in the given Binary Tree.

The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Below image represents a tree and LCA of different pair of nodes (N1, N2) in it:



Finding LCA

Method 1: The simplest method of finding LCA of two nodes in a Binary Tree is to observe that the LCA of the given nodes will be the last common node in the paths from the root node to the given nodes.

For Example: consider the above-given tree and nodes 4 and 5.
  • Path from root to node 4: [1, 2, 4]
  • Path from root to node 5: [1, 2, 5].
The last common node is 2 which will be the LCA.

Algorithm:
  1. Find the path from the root node to node n1 and store it in a vector or array.
  2. Find the path from the root node to node n2 and store it in another vector or array.
  3. Traverse both paths untill the values in arrays are same. Return the common element just before the mismatch.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

Analysis: The time complexity of the above solution is O(N) where N is the number of nodes in the given Tree and the above solution also takes O(N) extra space.

Method 2: The method 1 finds LCA in O(N) time but requires three tree traversals plus extra spaces for path arrays. If we assume that the keys are present in Binary Tree, we can find LCA using single traversal of Binary Tree and without extra storage for path arrays.

The idea is to traverse the tree starting from the root node. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn't match with any of the keys, we recur for left and right subtrees. The node which has one key present in its left subtree and the other key present in the right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise, LCA lies in the right subtree.

Below is the implementation of the above approach:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
LCA(4, 5) = 2nLCA(4, 6) = 1nLCA(3, 4) = 1nLCA(2, 4) = 2
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).



Solution: The diameter of a tree T is the largest of the following quantities:
  • The diameter of T's left subtree.
  • The diameter of T's right subtree.
  • The longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T).

The longest path between leaves that goes through a particular node say, nd can be calculated as:
1 + height of left subtree of nd + height of right subtree of nd

Therefore, final Diameter of a node can be calculated as:
Diameter = maximum(lDiameter, rDiameter, 1 + lHeight + rHeight)
Where,
lDiameter = Diameter of left subtree
rDiameter = Diameter of right subtree
lHeight = Height of left subtree
rHeight = Height of right subtree

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Diameter of the given binary tree is 4

Time Complexity: O(N2), where N is the number of nodes in the binary tree.
Problem: Given a Binary Tree. The task is to print the nodes of the binary tree when viewed from different sides. That is, the left view of the binary tree will contain only those nodes which can be seen when the Binary tree is viewed from left.

Example:
Consider the Below Binary Tree:


Left View of above Tree will be: 1, 2, 4
Right View of above Tree will be: 1, 3, 7
Top View of above Tree will be: 4, 2, 1, 3, 7
Bottom View of above Tree will be: 4, 5, 6, 7

Let us now look at each of the solutions in details:
  • Left View: A simple solution is to notice that the nodes appearing in the left view of the binary tree are the first nodes at every level. So, the idea is to do a level order traversal of the binary tree using a marker to identify levels and print the first node at every level.

    Below is the complete function to print left view:
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  • Right View: Printing Right View of the Binary Tree is similar to the above approach of printing the Left view of the tree. The idea is to print the last node present at every level. So, perform a level order traversal using a delimeter to identify levels and print the last node present at every level.

  • Top View: Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x is equal to the horizontal distance of x minus 1, and that of right child is the horizontal distance of x plus 1.

    So, the idea is to do a level order traversal of the tree and calculate the horizontal distance of every node from the root node and print those nodes which are the first nodes of a particular horizontal distance.

    Hashing can be used to keep a check on whether any node with a particular horizontal distance is encountered yet or not.

    Below is the function implementing the above approach:
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  • Bottom View: The Bottom View of a binary tree can be printed using the similar approach as that of printing the Top View. A node x is there in output if x is the bottom most instead of the top most node at its horizontal distance.

    The process of printing the bottom view is almost the same as that of top view with a little modification that while storing the node's data along with a particular horizontal distance in the map, keep updating the node's data in the map for a particular horizontal distance so that the map contains the last node appearing with a particular horizontal distance instead of first.

The Inorder traversal of a Binary tree can either be done using recursion or with the use of an auxiliary stack. Threaded Binary Trees are used to make the inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists).

There are two types of threaded binary trees:
  1. Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists).
  2. Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.

Note: The threads are also useful for fast accessing ancestors of a node.

Following diagram shows an example Single Threaded Binary Tree. The dotted lines represent threads.
threadedBT
Representation of a Threaded Node:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Since the right pointer in a Threaded Binary Tree is used for two purposes, the boolean variable rightThread is used to indicate whether the right pointer points to a right child or an inorder successor. Similarly, we can add leftThread for a double threaded binary tree.

Inorder Traversal in a Threaded Binary Tree: Below is the algorithm to perform inorder traversal in a Threaded Binary Tree using threads:
  1. Start from the root node, go to the leftmost node and print the node.
  2. Check if there is a thread towards the right for the current node.
    • If Yes, then follow the thread to the node and print the data of node linked with this thread.
    • Otherwise follow the link to the right subtree, find the leftmost node in the right subtree and print the leftmost node.
  3. Repeat the above process until the complete tree is traversed.

Following diagram demonstrates the inorder traversal in a Threaded Binary Tree:
threadedTraversal
Below functions implements the inorder traversal in a threaded binary tree:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Problem #1 : Print Nodes in Top View of Binary Tree

Description - Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. Expected time complexity is O(n)

A node x is there in output if x is the topmost node at its horizontal distance. The horizontal distance of left child of a node x is equal to a horizontal distance of x minus 1, and that of a right child is the horizontal distance of x plus 1.

Top view of the above binary tree is
4 2 1 3 7


Top view of the above binary tree is
2 1 3 6
Solution - The idea is to do something similar to vertical Order Traversal. Like vertical Order Traversal, we need to put nodes of same horizontal distance together. We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. Hashing is used to check if a node at a given horizontal distance is seen or not.
Pseudo Code
// function should print the topView of 
// the binary tree
void topview(Node* root)
{
if(root==NULL)
return;
queue < Node* > q
map < int,int > m
int hd=0
root->hd=hd

// push node and horizontal distance to queue
q.push(root);
while(!q.empty())
{
hd=root->hd
// check whether node at hd distance seen or not
if(m.find(hd)==false)
m[hd]=root->data
if(root->left)
{
root->left->hd=hd-1
q.push(root->left)
}
if(root->right)
{
root->right->hd=hd+1
q.push(root->right)
}
q.pop()
root=q.front()
}
for(it=m.begin();it!=m.end();it++)
{
print(it->second)
}
}

Problem #2 : Diameter of a Binary Tree

Description - The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

Solution - The diameter of a tree T is the largest of the following quantities:
  1. the diameter of T’s left subtree
  2. the diameter of T’s right subtree
  3. the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
Pseudo Code
int diameter(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0

/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0

if(root == NULL)
{
*height = 0
return 0 /* diameter is also 0 */
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameter(root->left, &lh)
rdiameter = diameter(root->right, &rh)

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1

return max(lh + rh + 1, max(ldiameter, rdiameter))
}

Problem #3 : Convert a Binary Tree into its Mirror Tree

Description - Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.Trees in the below figure are mirror of each other.
MirrorTree1
Solution - The idea is to recursively call for left and right subtrees of a given node. On each recursive call swap the pointers of the children nodes.
Pseudo Code
// function to convert binary tree to it's mirror
void mirror(struct Node* node)
{
if (node == NULL)
return
else
{
struct Node* temp

/* Recur for subtrees */
mirror(node->left)
mirror(node->right)

/* swap the pointers in this node */
temp = node->left
node->left = node->right
node->right = temp
}
}

Problem #4 : Convert a given Binary Tree to Doubly Linked List

Description - Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.
TreeToList Solution - The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.
Pseudo Code
// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
// Base case
if (root == NULL)
return

// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL

// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root->left, head)

// Now convert this node
if (prev == NULL)
*head = root
else
{
root->left = prev
prev->right = root
}
prev = root

// Finally convert right subtree
BinaryTree2DoubleLinkedList(root->right, head)
}

Question 1 [1 Marks]
Which of the following is a true about Binary Trees
A
Every binary tree is either complete or full.
B
Every complete binary tree is also a full binary tree.
C
Every full binary tree is also a complete binary tree.
D
No binary tree is both complete and full.
E
None of the above
Explanation

If you are facing any issue on this page. Please let us know.